﻿#include "ssAStar.h"


namespace StarSeeker
{

ssAStar::ssAStar()
{
	m_obstacleLevel = 0;
}

ssAStar::~ssAStar()
{
}

bool ssAStar::Init(ulint row, ulint colum, i8 * obstacleLevelArr, ulint arrSize)
{
	if (m_cellArr.Count())
	{
		return false;
	}
	if (row*colum != arrSize)
	{
		return false;
	}
	m_cellArr.Init(row, colum);
	for (ulint i = 0; i < arrSize; ++i)
	{
		m_cellArr[i] = obstacleLevelArr[i];
	}
	return true;
}

bool ssAStar::PathFinding(ulint beginRow, ulint beginColum, ulint endRow, ulint endColum)
{
	if (beginRow>m_cellArr.Row() || endRow>m_cellArr.Row() || beginColum>m_cellArr.Column() || endColum>m_cellArr.Column())
	{
		return false;
	}
	if (m_cellArr(beginRow, beginColum) == m_obstacleLevel || m_cellArr(endRow, endColum) == m_obstacleLevel)
	{
		return false;
	}
	GetAroundCell(endRow, endColum, endRow, endColum, m_tempCells);
	if (m_tempCells.Count()==0)
	{
		return false;
	}

	m_result.Empty();
	m_openList.Empty();
	m_closeList.Empty();
	ssAStarCell begin = { beginRow,beginColum,m_cellArr(beginRow,beginColum),SS_INVAILD_U32 };
	m_closeList.PushBack(begin);
	for (ulint k=0; k<m_cellArr.Count(); ++k)
	{
		//周围格子
		GetAroundCell(endRow, endColum, begin.row, begin.colum, m_tempCells);
		if (m_tempCells.Count() > 0)
		{
			//不重复插入
			for (ulint i = 0; i < m_tempCells.Count(); ++i)
			{
				if (m_closeList.ElementExists(m_tempCells[i]))
					continue;
				m_openList.PushBack(m_tempCells[i]);
			}
			//找最小值
			ssAStarCell min = m_openList[0];
			ulint offset = 0;
			for (ulint i = 1; i < m_openList.Count(); ++i)
			{
				if (m_openList[i].weight < min.weight)
				{
					offset = i;
					min = m_openList[i];
				}
			}
			//存最小值
			begin = min;
			m_openList.Remove(offset);
			m_closeList.PushBack(begin);
			//结束
			if (min.row == endRow && min.colum == endColum)
				break;
			if (m_openList.Count()==0)
				break;
		} 
		else
		{
			break;
		}
	}
	if (begin.row == endRow && begin.colum == endColum)
	{
		for (lint i = m_closeList.Length()-1; i >= 0;)
		{
			lint offset = i;
			m_result.PushBack(m_cellArr.SwitchOneDimensional(m_closeList[i].row, m_closeList[i].colum));
			for (lint j = 0; j < i; ++j)
			{
				ulint one = m_cellArr.SwitchOneDimensional(m_closeList[j].row, m_closeList[j].colum);
				if (m_closeList[i].father == one)
				{
					offset = j;
					break;
				}
			}
			if (offset!=i)
			{
				i = offset;
			} 
			else
			{
				--i;
			}
		}
		return true;
	}
	return false;
}

void ssAStar::GetResult(ssNumArray<ulint>& out, bool twoDimensional)
{
	out.Empty(false);

	for (lint i = m_result.Length() - 1; i >= 0; --i)
	{
		if (twoDimensional)
		{
			out.PushBack(m_cellArr.SwitchRow(m_result[i]));
			out.PushBack(m_cellArr.SwitchColumn(m_result[i]));
		} 
		else
		{
			out.PushBack(m_result[i]);
		}
	}
}

StarSeeker::i32 ssAStar::GetCellWeight(ulint endRow, ulint endColum, ulint row, ulint colum, bool isOblique)
{
	//寻路消耗=离起点距离+离终点距离
	int beg = isOblique ? 14 : 10;
	return beg + (abs((int)endRow - (int)row) * 10) + (abs((int)endColum - (int)colum) * 10);
}

void ssAStar::GetAroundCell(ulint endRow, ulint endColum, ulint row, ulint colum, ssNumArray<ssAStarCell, 8>& out)
{
	ssAStarCell temp = {};
	temp.father = m_cellArr.SwitchOneDimensional(row, colum);
	out.Empty(false);
	if (row<m_cellArr.Row()-1 && colum>0)//左上
	{
		temp.row = row + 1;
		temp.colum = colum - 1;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, true);
			out.PushBack(temp);
		}
	}
	if (row < m_cellArr.Row() - 1)//上
	{
		temp.row = row + 1;
		temp.colum = colum;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, false);
			out.PushBack(temp);
		}
	}
	if (row < m_cellArr.Row() - 1 && colum < m_cellArr.Column() - 1)//右上
	{
		temp.row = row + 1;
		temp.colum = colum + 1;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, true);
			out.PushBack(temp);
		}
	}
	if (colum > 0)//左
	{
		temp.row = row;
		temp.colum = colum-1;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, false);
			out.PushBack(temp);
		}
	}
	if (colum < m_cellArr.Column() - 1)//右
	{
		temp.row = row;
		temp.colum = colum + 1;
		if (m_cellArr(temp.row, temp.colum) != 0)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, false);
			out.PushBack(temp);
		}
	}
	if (row>0 && colum>0)//左下
	{
		temp.row = row - 1;
		temp.colum = colum - 1;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, true);
			out.PushBack(temp);
		}
	}
	if (row>0)//下
	{
		temp.row = row - 1;
		temp.colum = colum;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, false);
			out.PushBack(temp);
		}
	}
	if (row > 0 && colum < m_cellArr.Column() - 1)//右下
	{
		temp.row = row - 1;
		temp.colum = colum + 1;
		if (m_cellArr(temp.row, temp.colum) != m_obstacleLevel)
		{
			temp.weight = GetCellWeight(endRow, endColum, temp.row, temp.colum, true);
			out.PushBack(temp);
		}
	}
}

}
